package cxydmmszl.chapter08.t118;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

/**
 * <li style="color: red;">Prob</li>
 * 找到无序数组中最小的 k 个数
 * <li style="color: green;">Desc</li>
 * 给定一个整型数组 arr，找到其中最小的 k 个数。
 * <br/><br/>备注：<br/>
 * 时间复杂度 O(nlogk) 和 O(n)，额外空间复杂度 O(n)。
 * <li style="color: green;">Input</li>
 * 输入包含两行，第一行包含两个整数 n 和 k(1≤k≤n≤10^5)，
 * 代表数组 arr 的长度，第二行包含 n 个整数，代表数组 arr(1≤arr[i]≤10^9)。
 * <li style="color: green;">Output</li>
 * 输出包含一行，k 个整数，代表数组中最小的 k 个整数。
 * <li style="color: blue;">Link</li> CD152
 *
 * @author habitplus
 * @since 2021-10-09 14:43
 */
public class Main {
    static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() {
        try {
            st.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) st.nval;
    }

    public static void main(String[] args) {
        int n = nextInt();
        int k = nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nextInt();
        }

        int[] ans = minKNumbersByHeap(arr, k);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < k; i++) {
            sb.append(ans[i]).append(' ');
        }
        System.out.println(sb.toString());
    }

    /*
        直接排序：O(NlogN)
     */
    public static int[] minKNumbersBySort(int[] arr, int k) {
        if (arr == null || arr.length == 0 || k < 1 || k > arr.length) {
            return new int[0];
        }
        Arrays.sort(arr);
        int[] res = new int[k];
        System.arraycopy(arr, 0, res, 0, k);
        return res;
    }

    /*
        维持一个大小为 k 大顶堆：O(NlogK)
     */
    public static int[] minKNumbersByHeap(int[] arr, int k) {
        if (arr == null || arr.length == 0 || k < 1 || k > arr.length) {
            return new int[0];
        }

        int n = arr.length;

        int[] heap = new int[k];

        for (int i = 0; i < k; i++) {
            heap[i] = arr[i];
            heapInsert(heap, i);
        }

        for (int i = k; i < n; i++) {
            if (heap[0] > arr[i]) {
                heap[0] = arr[i];
                heapify(heap, 0, k);
            }
        }

        return heap;
    }

    private static void heapify(int[] heap, int p, int heapSize) {
        int lch = p * 2 + 1; // the index of left child
        int rch = p * 2 + 1; // the index of right child
        int li = p;         // the index of largest number
        while (lch < heapSize) {
            if (heap[lch] > heap[li]) {
                li = lch;
            }

            if (rch < heapSize && heap[rch] > heap[li]) {
                li = rch;
            }

            if (li == p) break;

            swap(heap, p, li);
            p = li;
            lch = 2 * p + 1;
            rch = 2 * p + 2;
        }
    }

    private static void heapInsert(int[] heap, int k) {
        // 调整堆
        int parent;
        while (k != 0) {
            parent = (k - 1) / 2;
            if (heap[parent] < heap[k]) {
                swap(heap, parent, k);
            } else {
                break;
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        arr[i] ^= arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] ^= arr[j];
    }
}
